﻿#include <iostream>

#define STREET '.'
#define BLOCK 'X'

static int howManyAtLeast(const char* street, size_t size)
{
    int lightCount = 0;
    int index = 0;
    while (index < size)
    {
        char cur = street[index];
        if (cur == BLOCK)
        {
            ++index;
            continue;
        }

        if (index + 1 < size)
        {
            if (street[index + 1] == STREET)
            {
                index += 3;
            }
            else
            {
                index += 2;
            }

            ++lightCount;
        }
        else
        {
            ++lightCount;
            ++index;
        }
    }

    return lightCount;
}

// 小Q正在给一条长度为n的道路设计路灯安置方案。
// 为了让问题更简单，小Q把道路视为n个方格，需要照亮的地方用'.'表示，不需要照亮的障碍物格子用'X'表示。
// 小Q现在要在道路上设置一些路灯，对于安置在pos位置的路灯，这盏路灯可以照亮pos - 1，pos，pos + 1三个位置。
// 小Q希望能安置尽量少的路灯照亮所有'.'区域。希望你能帮他计算一下最少需要多少盏路灯。
//
//输入描述：
// 输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
// 接下来每两行一个测试数据，第一行一个正整数n(1 <= n <= 1000), 表示道路的长度，第二行一个字符串a表示道路的构造，
// 只包含'.'和'X'。
//
//输出描述:
//对于每个测试用例，输出一个正整数表示最少需要多少盏路灯。
//
//思路：
// 方法1 : 动态规划，从左往右
//
//方法2 : 贪心策略，看第i个位置，如果是'X'，则无法放置路灯；
// 如果是'.'，则看i + 1是啥，如果i + 1是'X', 则当前需要放置路灯，然后跳到i + 2位置；
// 如果i + 1是'.', 则也要放置，只不过这个时候i + 1可以跳过了，考虑到一个路灯可以辐射3个位置，故可以直接跳到i + 3位置进行判断了。
int main_StreetLamp()
{
    char input[][256] = {
        "6",
        "10",
        "..........",
        "5",
        "..X..",
        "7",
        "...XX..",
        "11",
        "...........",
        "12",
        "XXXXXXXX...X",
        "15",
        "..XX.X.X..X....",
    };

    int exampleCount = 0;
    sscanf_s(input[0], "%d", &exampleCount);
	
    for (int i = 0; i < exampleCount; i++)
    {
        int size = 0;
        sscanf_s(input[1 + i * 2], "%d", &size);
        int len = strlen(input[1 + i * 2 + 1]);
        if (len != size)
        {
            size = len;
        }

        printf("%d\n", howManyAtLeast(input[1 + i * 2 + 1], size));
    }

    return 0;
}